//滑动窗口算法记录： https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485141&idx=1&sn=0e4583ad935e76e9a3f6793792e60734&chksm=9bd7f8ddaca071cbb7570b2433290e5e2628d20473022a5517271de6d6e50783961bebc3dd3b&scene=21#wechat_redirect

/**
 * 滑动窗口 76.最小覆盖子串
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 */
var minWindow = function(s, t) {
    let needs = {},window = {};
    for(let w of t){
        needs[w] ? needs[w]++ : needs[w] = 1;
    }
    let keyLen = Object.keys(needs).length;
    let valid = 0;
    let left = right = 0;
    let start = 0,len=Number.MAX_SAFE_INTEGER;
    while(right<s.length){
        let d = s[right];
        right++;
        window[d] ? window[d]++ : window[d] = 1;
        if(window[d] === needs[d]){
            valid++;
        }
 
        while(valid==keyLen){
            if(right-left < len){
                len = right - left;
                start = left;
            }
            let c = s[left];
            left++;
            if(needs[c]){
                if(window[c] === needs[c]){
                    valid--;
                }
                window[c]--
            }
        }
    }
    return len==Number.MAX_SAFE_INTEGER ? '' : s.substr(start,len);
 };


/**
 * 滑动窗口 567.字符串的排列
 * 输入: s1 = "ab" s2 = "eidbaooo"
 * 输出: True
 * 解释: s2 包含 s1 的排列之一 ("ba").
 */
var checkInclusion = function(s1, s2) {
    let needs = {},window = {};
    for(let w of s1){
        needs[w] ? needs[w]++ : needs[w] = 1;
    }
    let keyLen = Object.keys(needs).length;
    let left = right = valid = 0;
    while(right < s2.length){
        let r = s2[right];
        right++;
        window[r]? window[r]++ : window[r] = 1;
        if(window[r]===needs[r]){
            valid++;
        }

        while(right - left >= s1.length){
            if(valid == keyLen) {return true};
            let l = s2[left];
            left++;
            if(needs[l]){
                if(window[l] === needs[l]){
                    valid--;
                }
                window[l]--;
            }
        }
    }
    return false;
};


/**
 * 滑动窗口 438.找到字符串中所有字母异位词
    输入: s: "cbaebabacd" p: "abc"
    输出: [0, 6]
    解释:
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
 */
var findAnagrams = function(s, p) {
    let needs = {},window = {};
    for(let w of p){
        needs[w] ? needs[w]++ : needs[w] = 1;
    }
    let keyLen = Object.keys(needs).length;
    let left = right = valid = 0;
    let res = [];
    while(right < s.length){
        let r = s[right];
        right++;
        window[r]? window[r]++ : window[r] = 1;
        if(window[r]===needs[r]){
            valid++;
        }

        while(right - left >= p.length){
            if(valid == keyLen) {res.push(left)};
            let l = s[left];
            left++;
            if(needs[l]){
                if(window[l] === needs[l]){
                    valid--;
                }
                window[l]--;
            }
        }
    }
    return res;
};

/**
 * 滑动窗口 3.最长无重复子串
   输入: s = "abcabcbb"
   输出: 3 
   解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 */
var lengthOfLongestSubstring = function(s) {
   if(s.length == 0) return 0;
   let res = 0;
   let left = right = 0;
   let window = {};
   while(right<s.length){
        let r = s[right];
        right++;
        window[r] ? window[r]++ : window[r] = 1;

        while(window[r]>1){
            let l = s[left];
            left++;
            window[l]--;
        }
        res = Math.max(res,right-left);
   }
   return res;
};

/**
 * 滑动窗口 239.滑动窗口最大值
  输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
  输出：[3,3,5,5,6,7]
 */
var maxSlidingWindow = function(nums, k) {
   let res = [],window=[];
   for(let i=0;i<nums.length;i++){
        if(i-window[0]>=k){
            window.shift();
        }
        while(nums[window[window.length - 1]]<= nums[i]){
            window.pop();
        }
        window.push(i);
        if(i >=k-1){
            res.push(nums[window[0]]);
        }
    }
    return res;
};